import bisect
from typing import List


# 给定一个含有 n 个正整数的数组和一个正整数 target。
# 找出该数组中满足其总和大于等于 target 的长度最小的 连续
# 子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
# 使用滑动窗口的方式
# 时间复杂度：O(n)，start_inde 和 end_index 最多移动 n 次
# 空间复杂度：O(1)
def minSubArrayLen(target: int, nums: List[int]) -> int:
    start_index = 0
    end_index = -1
    num_sum = 0
    nums_len = len(nums)
    re = 0

    while end_index < nums_len:
        while num_sum < target and end_index < nums_len - 1:
            end_index += 1
            num_sum += nums[end_index]
        # 找到了，连续和
        if num_sum >= target:
            if re == 0:
                re = end_index - start_index + 1
            re = min(re, end_index - start_index + 1)
            # 开始找下一个
            num_sum -= nums[start_index]
            start_index += 1
        else:
            # 遍历到最后一个元素，也无法找到
            break

    return re


# 使用前缀和+二分查找的方式
# 时间复杂度：O(nlogn)，使用二分查找的方式
# 空间复杂度：O(n)，需要创建一个额外的数组存储前缀和
def minSubArrayLen_prefixAndBinarySearch(target: int, nums: List[int]) -> int:
    nums_len = len(nums)
    re = 0
    # 前缀和数组
    nums_sum = list()
    nums_sum.append(nums[0])
    for i in range(1, nums_len):
        nums_sum.append(nums_sum[-1] + nums[i])

    temp_target = target
    for i in range(nums_len):
        if i != 0:
            temp_target = temp_target + nums[i - 1]
        # bound 是前缀和的索引，如果找不到索引，会返回nums_sum的长度
        bound = bisect.bisect_left(nums_sum, temp_target)
        # 第一次找到符合条件的前缀和
        if re == 0 and bound != nums_len:
            re = bound - i + 1
        # 能找到，取最小连续数组的大小
        if bound != nums_len:
            re = min(re, bound - i + 1)
        print(f"nums_sum:{nums_sum} , bound:{bound}")
    return re


target_1 = 7
nums_1 = [2, 3, 1, 2, 4, 3]
result = minSubArrayLen_prefixAndBinarySearch(target_1, nums_1)
print(f"result:{result}")

target_2 = 4
nums_2 = [1, 4, 4]
result = minSubArrayLen_prefixAndBinarySearch(target_2, nums_2)
print(f"result:{result}")

target_3 = 4
nums_3 = [1, 1, 1]
result = minSubArrayLen_prefixAndBinarySearch(target_3, nums_3)
print(f"result:{result}")

target_4 = 1
nums_4 = [1, 4, 9]
result = minSubArrayLen_prefixAndBinarySearch(target_4, nums_4)
print(f"result:{result}")
